//
// Created by PC on 2017/12/22.
//

#ifndef DFSANDCOMPONENTS_PATH_H
#define DFSANDCOMPONENTS_PATH_H
#include <iostream>
#include <vector>
#include <cassert>
#include <stack>

using namespace std;
template <typename Graph>
class Path{
private:
    int s;
    Graph &G;
    bool *visited;
    int *from;
    void dfs(int v) {
        visited[v]=true;
        typename Graph::adjIterator adj(G,v);
        for (int w = adj.begin(); !adj.end(); w = adj.next())
            if (!visited[w]) {
                from[w]=v;
                dfs(w);
            }
    }
public:
    Path(Graph &graph, int s) : G(graph) {

        assert(s>=0 && s<G.V());
        this->s=s;
        visited=new bool[G.V()];
        from=new int[G.V()];
        for (int i = 0; i < G.V(); i++) {
            visited[i]=false;
            from[i]=-1;
        }

        dfs(s);
    }
    ~Path(){
        delete[] visited;
        delete[] from;
    }

    bool hasPath(int w){
        assert(w>=0 && w<G.V());
        return visited[w];
    }
    void path(int w,vector<int> &vec){
        assert(hasPath(w));
        stack<int> stack1;
        int p=w;
        while (p != -1) {
            stack1.push(p);
            p=from[p];
        }
        vec.clear();
        while (!stack1.empty()) {
            vec.push_back(stack1.top());
            stack1.pop();
        }
    }
    void showPath(int w){
        assert(hasPath(w));
        vector<int> vec;
        path(w,vec);
        for (int i = 0; i < vec.size(); i++) {
            cout<<vec[i];
            if(i<vec.size()-1)
                cout<<" -> ";
            else
                cout<<endl;
        }
    }
};

#endif //DFSANDCOMPONENTS_PATH_H
